package com.captain.leetcode.链表;

import java.util.List;

/**
 * Des:
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 * 输入：head = [1,2,3,4,5], left = 2, right = 4
 * 输出：[1,4,3,2,5]
 * <p>
 * 输入：head = [5], left = 1, right = 1
 * 输出：[5]
 *
 * @author XL
 * @Date 2021/8/9 11:58
 */
public class 反转链表II92 {
    public static void main(String[] args) {
        new 反转链表II92().reverseBetween(ListNode.getInstance(), 2, 4);
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        //  * 输入：head = [1,2,3,4,5], left = 2, right = 4
        // * 输出：[1,4,3,2,5]
        ListNode dummyNode = new ListNode(-1);
        //哑节点
        dummyNode.next = head;
        //操作节点
        ListNode cur = dummyNode;
        //找到左节点
        for (int i = 0; i < (left - 1); i++) {
            cur = cur.next;
        }
        //继续遍历找到右节点
        ListNode rightNode = cur;
        for (int i = 0; i < (right - left + 1); i++) {
            rightNode = rightNode.next;
        }
        ListNode leftNode = cur.next;
        //右接点
        ListNode backCurr = rightNode.next;
        //左连接点 cur.next = leftNode
        //切出子链表
        cur.next = null;
        rightNode.next = null;
        //翻转链表
        leftNode = reverseLinkedList(leftNode);
        cur.next = leftNode;
        ListNode tp = cur;
        while (tp.next != null) {
            tp = tp.next;
        }
        tp.next = backCurr;
        return dummyNode.next;
    }

    private ListNode reverseLinkedList(ListNode head) {
        // 翻转链表
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
